{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Way to Form String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestWay"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #形成字符串的最短路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>对于任何字符串，我们可以通过删除其中一些字符（也可能不删除）来构造该字符串的 <strong>子序列</strong> 。(例如，<code>“ace”</code>&nbsp;是 <code>“abcde”</code> 的子序列，而 <code>“aec”</code> 不是)。</p>\n",
    "\n",
    "<p>给定源字符串&nbsp;<code>source</code> 和目标字符串&nbsp;<code>target</code>，返回 <em>源字符串&nbsp;<code>source</code>&nbsp;中能通过串联形成目标字符串&nbsp;</em><code>target</code>&nbsp;<em>的 <strong>子序列</strong> 的最小数量&nbsp;</em>。如果无法通过串联源字符串中的子序列来构造目标字符串，则返回&nbsp;<code>-1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>source = \"abc\", target = \"abcbc\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>目标字符串 \"abcbc\" 可以由 \"abc\" 和 \"bc\" 形成，它们都是源字符串 \"abc\" 的子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>source = \"abc\", target = \"acdbc\"\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>由于目标字符串中包含字符 \"d\"，所以无法由源字符串的子序列构建目标字符串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>source = \"xyz\", target = \"xzyxz\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>目标字符串可以按如下方式构建： \"xz\" + \"y\" + \"xz\"。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= source.length, target.length &lt;= 1000</code></li>\n",
    "\t<li><code>source</code> 和&nbsp;<code>target</code>&nbsp;仅包含英文小写字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-way-to-form-string](https://leetcode.cn/problems/shortest-way-to-form-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-way-to-form-string](https://leetcode.cn/problems/shortest-way-to-form-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"\\n\"abcbc\"', '\"abc\"\\n\"acdbc\"', '\"xyz\"\\n\"xzyxz\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        # 问题改写：重复n次source，使target是n*source的子序列，返回n\n",
    "        def is_subseq(t, s):# 判断t是否是s的子序列\n",
    "            m, n = len(t), len(s)\n",
    "            # 双指针\n",
    "            i, j = 0, 0\n",
    "            while i < m and j < n:\n",
    "                if t[i] == s[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            return i == m\n",
    "        for ch in set(target):\n",
    "            if ch not in set(source):\n",
    "                return -1\n",
    "        \n",
    "        source_repeated = source\n",
    "        ans = 1\n",
    "        while not is_subseq(target, source_repeated):\n",
    "            source_repeated += source\n",
    "            ans += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        m=len(source)\n",
    "        n = len(target)\n",
    "        j=0\n",
    "\n",
    "        Flag = True\n",
    "        ans = 0\n",
    "        while Flag:\n",
    "            Flag=False\n",
    "            for i in range(m):\n",
    "                if j<n and source[i]==target[j]:\n",
    "                    j+=1\n",
    "                    Flag = True\n",
    "            ans+=1\n",
    "            if j==n:\n",
    "                break\n",
    "            \n",
    "        \n",
    "        return ans if j==n else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        q = 0\n",
    "        p = 0\n",
    "        cnt = 0\n",
    "        eles = set(source)\n",
    "        while q < len(target):\n",
    "            if target[q] not in eles:\n",
    "                return -1\n",
    "            if source[p] == target[q]:\n",
    "                q += 1\n",
    "                if q == len(target):\n",
    "                    cnt += 1\n",
    "                    break\n",
    "            p += 1\n",
    "            if p == len(source):\n",
    "                cnt += 1\n",
    "                p = 0\n",
    "        \n",
    "        if q < len(target):\n",
    "            return -1\n",
    "        else:\n",
    "            return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ifSubStr(self, a: str, b: str) -> bool:\n",
    "            n = len(a)\n",
    "            m = len(b)\n",
    "            i = 0\n",
    "            j = 0\n",
    "            if n>m:\n",
    "                return False\n",
    "            for i in range(n):\n",
    "                while j<m and b[j]!=a[i]:\n",
    "                    j+=1\n",
    "                if j==m:\n",
    "                    return False\n",
    "                j+=1\n",
    "            return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        n = len(target)\n",
    "        temp = \"\"\n",
    "\n",
    "        dp=[0]*n\n",
    "        if target[0] not in source:\n",
    "            return -1\n",
    "        else:\n",
    "            temp = target[0]\n",
    "            dp[0] = 1\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if target[i] not in source:\n",
    "                return -1\n",
    "            else:\n",
    "                temp+=target[i]\n",
    "                check = self.ifSubStr(temp,source)\n",
    "                #print(temp,source,check)\n",
    "                if check:\n",
    "                    dp[i] = dp[i-1]\n",
    "                else:\n",
    "                    temp = target[i]\n",
    "                    dp[i] = dp[i-1]+1\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        # 最短路径问题，典型的动态规划\n",
    "        result = 0\n",
    "        i = 0\n",
    "        while i < len(target):\n",
    "            pred_i = i\n",
    "            for j in range(len(source)):\n",
    "                if target[i] == source[j]:\n",
    "                    i += 1\n",
    "                if i >= len(target):\n",
    "                    break\n",
    "            if pred_i < i:\n",
    "                result += 1\n",
    "            else:\n",
    "                return -1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        m, n = len(source), len(target)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        flag = True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            for i in range(m):\n",
    "                if j < n and source[i] == target[j]:\n",
    "                    flag = True\n",
    "                    j += 1\n",
    "            ans += 1\n",
    "            if j == n:\n",
    "                break          \n",
    "        return ans if j == n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, s: str, target: str) -> int:\n",
    "        n,m=len(s),len(target)\n",
    "        i,res=0,0\n",
    "        while i<m:\n",
    "            j=0\n",
    "            pre=i\n",
    "            while i<m and j<n:\n",
    "                if target[i]==s[j]:\n",
    "                    i+=1\n",
    "                j+=1\n",
    "            if pre==i: return -1\n",
    "            res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        n = len(target)\n",
    "        j = 0\n",
    "        res = 0 \n",
    "        flag = True\n",
    "        while(flag):\n",
    "            flag = False\n",
    "            for i in range(len(source)):\n",
    "                if source[i]==target[j]:\n",
    "                    flag=True\n",
    "                    j+=1\n",
    "                if j==len(target):\n",
    "                    break\n",
    "            \n",
    "            res+=1\n",
    "            if j==len(target):\n",
    "                break\n",
    "        \n",
    "        return res if j==len(target) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        m, n = len(source), len(target)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        flag = True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            for i in range(m):\n",
    "                if j < n and source[i] == target[j]:\n",
    "                    flag = True\n",
    "                    j += 1\n",
    "            ans += 1\n",
    "            if j == n:\n",
    "                break          \n",
    "        return ans if j == n else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        i,res = 0,0\n",
    "        m,n = len(source),len(target)\n",
    "        while i<n:\n",
    "            tmp = i\n",
    "            res+=1\n",
    "            for j in range(m):\n",
    "                if i<n and source[j]==target[i]:\n",
    "                    i+=1\n",
    "            if tmp==i: return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        i = 0\n",
    "        n = len(target)\n",
    "        m = len(source)\n",
    "        count = 0\n",
    "        while i < n:\n",
    "            left = 0\n",
    "            while left < m and i < n:\n",
    "                if target[i] not in source:\n",
    "                    return -1\n",
    "                if target[i] == source[left%m]:\n",
    "                    left += 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    left += 1\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        S = set(source)\n",
    "        p, ans = len(source) - 1, 0\n",
    "        def move(p: int, ans: int) -> Tuple[int, int]:\n",
    "            p += 1\n",
    "            if p == len(source):\n",
    "                p = 0\n",
    "                ans += 1\n",
    "            return p, ans\n",
    "        for c in target:\n",
    "            if c not in S:\n",
    "                return -1\n",
    "            p, ans = move(p, ans)\n",
    "            while source[p] != c:\n",
    "                p, ans = move(p, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        res = i = 0\n",
    "        while i < len(target):\n",
    "            j = 0\n",
    "            pre = i\n",
    "            while i < len(target) and j < len(source):\n",
    "                if target[i] == source[j]:i+=1\n",
    "                j+=1\n",
    "            if pre == i:return -1\n",
    "            res += 1\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        m, n = len(source), len(target)\n",
    "        ans = 0# 子序列 的最小数量\n",
    "        j = 0# 用于遍历目标字符串的指针\n",
    "        flag = True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            for i in range(m):\n",
    "                if j < n and source[i] == target[j]:\n",
    "                    flag = True\n",
    "                    j += 1\n",
    "            ans += 1\n",
    "            if j == n:#遍历完目标数组之后是是相等的，即可退出while循环\n",
    "                break          \n",
    "        return ans if j == n else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, s: str, target: str) -> int:\n",
    "        #贪心+双指针\n",
    "        n,m=len(s),len(target)\n",
    "        i,res=0,0\n",
    "        while i<m:\n",
    "            j=0\n",
    "            pre=i\n",
    "            while pre<m and j<n:\n",
    "                if target[pre]==s[j]:\n",
    "                    pre+=1\n",
    "                j+=1\n",
    "            if pre==i: return -1\n",
    "            i=pre\n",
    "            res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        t = 0\n",
    "        res = 0\n",
    "        while t<len(target):\n",
    "            s = 0\n",
    "            if not target[t] in source:\n",
    "                return -1\n",
    "            while t<len(target) and s<len(source):\n",
    "                if target[t]==source[s]:\n",
    "                    t += 1\n",
    "                s += 1\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        m = len(source)\n",
    "        n = len(target)\n",
    "        i, j = 0, 0\n",
    "        res = 0\n",
    "        while j <= n-1:\n",
    "            i = 0\n",
    "            pre = j\n",
    "            while i <= m-1 and j <= n-1:\n",
    "                if source[i] == target[j]:\n",
    "                    j += 1\n",
    "                i += 1\n",
    "            if pre == j:    return -1\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        n = len(source)\n",
    "        j = 0\n",
    "        count = 0\n",
    "        while j < len(target):\n",
    "            prev = j \n",
    "            for i in range(n):\n",
    "                if j<len(target) and source[i]==target[j]:\n",
    "                    j+=1\n",
    "            if prev==j:\n",
    "                return -1\n",
    "            count += 1\n",
    "        return count\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        if set(target) - set(source): # 判断目标串是否存在不属于源串的字符\n",
    "            return -1\n",
    "        N, M = len(source), len(target)\n",
    "        dp = [0] * M\n",
    "        dp[0] = 1\n",
    "        tmp = source.index(target[0]) # 源串最左端的当前目标字符作为起点\n",
    "        for i in range(1,M):\n",
    "            if target[i] not in source[tmp+1:]:\n",
    "                dp[i] = dp[i-1] + 1 \n",
    "                tmp = source.index(target[i])  # 如果源串后面的范围不存在目标字符，说明源子串长度截止，获得源串最左端的当前目标字符作为新的起点，同时，子串个数+1\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "                tmp += source[tmp+1:].index(target[i]) + 1  # 如果在后面的范围里存在，那么tmp跳到那个存在的位置\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        count = 1\n",
    "        prev = -1\n",
    "        for i in range(len(target)):\n",
    "            ch = target[i]\n",
    "            if prev == len(source)-1:\n",
    "                prev = -1\n",
    "                count += 1\n",
    "            pos = source[prev+1:].find(ch) + prev + 1\n",
    "            if pos <= prev :\n",
    "                prev = -1\n",
    "                pos = source[prev+1:].find(ch) + prev + 1\n",
    "                if pos < 0:\n",
    "                    return -1\n",
    "                else:\n",
    "                    count += 1\n",
    "            prev = pos\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        # 这题适合贪心不适合dp\n",
    "        # 每轮遍历都找到最长的子序列，最后子序列的数量一定最小\n",
    "        m = len(source)\n",
    "        n = len(target)\n",
    "        i, j = 0, 0\n",
    "        res = 0\n",
    "        while j <= n-1:\n",
    "            i = 0 # 每轮迭代都从头开始\n",
    "            pre = j # 记录j刚开始的索引\n",
    "            while i <= m-1 and j <= n-1:\n",
    "                if source[i] == target[j]:\n",
    "                    j += 1 # 如果找到了，i和j都右移1位\n",
    "                i += 1 # 如果没找到，i右移1位\n",
    "            # 遍历完一轮\n",
    "            # 如果一个j都没找到，即j索引没变\n",
    "            if pre == j:    return -1 # 无法组成目标字符串\n",
    "            # 每轮遍历都对应一个子字符串\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        i, j = 0, 0\n",
    "        res = 0\n",
    "\n",
    "        while j < len(target):\n",
    "            if i == 0:\n",
    "                res += 1\n",
    "            if source[i] == target[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif target[j] not in source:\n",
    "                return -1\n",
    "            else:\n",
    "                i += 1\n",
    "            i %= len(source)\n",
    "\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        count=1\n",
    "        t=defaultdict(list)\n",
    "\n",
    "        for i in range(len(source)):\n",
    "            t[source[i]].append(i)\n",
    "        start=-1\n",
    "\n",
    "        for i in range(len(target)):\n",
    "            if target[i] not in t:\n",
    "                return -1\n",
    "            s=t[target[i]]\n",
    "            if s[-1]<=start:\n",
    "                start=s[0]\n",
    "                count+=1\n",
    "            else:\n",
    "                for c in s:\n",
    "                    if c>start:\n",
    "                        start=c\n",
    "                        break\n",
    "        return count\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source, target):\n",
    "        ls, lt = len(source), len(target)\n",
    "        i = 0\n",
    "        res = 0\n",
    "        while i < lt:\n",
    "            flag = 0\n",
    "            for j in range(ls):\n",
    "                if i < lt and source[j] == target[i]:\n",
    "                    i += 1\n",
    "                    flag = 1\n",
    "            if not flag:\n",
    "                return -1\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        m = len(source)\n",
    "        n = len(target)\n",
    "        i, j = 0, 0\n",
    "        res = 0\n",
    "        while j <= n-1:\n",
    "            i = 0 # 每轮迭代都从头开始\n",
    "            pre = j # 记录j刚开始的索引\n",
    "            while i <= m-1 and j <= n-1:\n",
    "                if source[i] == target[j]:\n",
    "                    j += 1 # 如果找到了，i和j都右移1位\n",
    "                i += 1 # 如果没找到，i右移1位\n",
    "            # 遍历完一轮\n",
    "            # 如果一个j都没找到，即j索引没变\n",
    "            if pre == j:    return -1 # 无法组成目标字符串\n",
    "            # 每轮遍历都对应一个子字符串\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        # 贪心迭代法 双指针\n",
    "        for char in target:\n",
    "            if char not in source:\n",
    "                return -1\n",
    "        count = 0\n",
    "        n = len(source)\n",
    "        # 源指针\n",
    "        source_iterator = 0\n",
    "        for char in target:\n",
    "            # 每次源指针复原，说明开始寻找新的子序列\n",
    "            if source_iterator == 0:\n",
    "                count+=1\n",
    "            while source[source_iterator] != char:\n",
    "                source_iterator = (source_iterator + 1) % n\n",
    "                if source_iterator == 0:\n",
    "                    count+=1\n",
    "            source_iterator = (source_iterator + 1) % n\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        # source index\n",
    "        sIdx = 0\n",
    "        # target index\n",
    "        tIdx = 0\n",
    "        res = 0\n",
    "        while sIdx < len(source) and tIdx < len(target):\n",
    "            if target[tIdx] == source[sIdx]:\n",
    "                res += 1\n",
    "                while sIdx < len(source) and tIdx < len(target):\n",
    "                    if target[tIdx] == source[sIdx]:\n",
    "                        tIdx += 1\n",
    "                    sIdx += 1\n",
    "                sIdx = 0\n",
    "            else:\n",
    "                sIdx += 1\n",
    "        return -1 if res == 0 or tIdx != len(target) else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "\n",
    "        # 检查  to_check 是否是 in_string 的子序列\n",
    "        def is_subsequence(to_check, in_string):\n",
    "            i = j = 0\n",
    "            while i < len(to_check) and j < len(in_string):\n",
    "                if to_check[i] == in_string[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "\n",
    "            return i == len(to_check)\n",
    "\n",
    "        # source 中所有字符的集合。也可以用一个布尔数组。\n",
    "        source_chars = set(source)\n",
    "\n",
    "        # 检查源文件中是否存在目标文件的所有字符\n",
    "        # 如果没有任何字符，返回 -1\n",
    "        for char in target:\n",
    "            if char not in source_chars:\n",
    "                return -1\n",
    "\n",
    "        # 串联 source 直到 target 是串联字符串的子序列。\n",
    "        concatenated_source = source\n",
    "        count = 1\n",
    "        while not is_subsequence(target, concatenated_source):\n",
    "            concatenated_source += source\n",
    "            count += 1\n",
    "\n",
    "        # 完成的串联数\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, s: str, target: str) -> int:\n",
    "        n,m=len(s),len(target)\n",
    "        i,res=0,0\n",
    "        while i<m:\n",
    "            j=0\n",
    "            pre=i\n",
    "            while i<m and j<n:\n",
    "                if target[i]==s[j]:\n",
    "                    i+=1\n",
    "                j+=1\n",
    "            if pre==i: return -1\n",
    "            res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source, target):\n",
    "        res = 0\n",
    "        ls, lt = len(source), len(target)\n",
    "        i = j = 0\n",
    "        flag = 0\n",
    "        while i < lt:\n",
    "            if source[j] == target[i]:\n",
    "                i += 1\n",
    "                flag = 1\n",
    "            j += 1\n",
    "            if j >= ls:\n",
    "                if flag:\n",
    "                    res += 1\n",
    "                else:\n",
    "                    return -1\n",
    "                j = 0\n",
    "                flag = 0\n",
    "        return res if j == 0 else res + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        for i in range(len(source)):\n",
    "            mp[source[i]].append(i)\n",
    "        ans, pre = 1, -1\n",
    "        for c in target:\n",
    "            if c not in mp: return -1\n",
    "            p = bisect_right(mp[c], pre)\n",
    "            if p != len(mp[c]):\n",
    "                pre = mp[c][p]\n",
    "            else:\n",
    "                ans += 1\n",
    "                pre = mp[c][0]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "            m, n = len(source), len(target)\n",
    "            j = 0\n",
    "            ans = 0\n",
    "            flag = True\n",
    "            while flag:\n",
    "                flag = False\n",
    "                for i in range(m):\n",
    "                    if j < n and source[i] == target[j]:\n",
    "                        flag = True\n",
    "                        j += 1\n",
    "                ans += 1\n",
    "                if j == n:\n",
    "                    break\n",
    "            return ans if j==n else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source, target):\n",
    "        source_chars = set(source)\n",
    "        for char in target:\n",
    "            if char not in source_chars:\n",
    "                return -1\n",
    "        m = len(source)\n",
    "        source_iterator = 0\n",
    "        count = 0\n",
    "        for char in target:\n",
    "            if source_iterator == 0:\n",
    "                count += 1\n",
    "            while source[source_iterator] != char:\n",
    "                source_iterator = (source_iterator + 1) % m\n",
    "                if source_iterator == 0:\n",
    "                    count += 1\n",
    "            source_iterator = (source_iterator + 1) % m\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        m, n = len(source), len(target)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        i = 0\n",
    "        tag = False\n",
    "        for j in range(n):\n",
    "            \n",
    "            while i < m:\n",
    "                if source[i] == target[j]:\n",
    "                    tag = True\n",
    "                    if i == m - 1:\n",
    "                        res += 1\n",
    "                        tag = False\n",
    "                        i = 0\n",
    "                        break\n",
    "                    i += 1\n",
    "                    break\n",
    "                else:\n",
    "                    if i == m - 1:\n",
    "                        if tag:\n",
    "                            res += 1\n",
    "                            tag = False\n",
    "                            i = 0\n",
    "                            continue\n",
    "                        else:\n",
    "                            return -1\n",
    "                \n",
    "                i += 1\n",
    "        if tag:\n",
    "            res += 1\n",
    "        return res\n",
    "                    \n",
    "                    \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        def _check_subsequence(to_check, in_string):\n",
    "            to_check_len, in_string_len = len(to_check), len(in_string)\n",
    "            to_check_index = in_string_index = 0\n",
    "\n",
    "            while to_check_index < to_check_len and in_string_index < in_string_len:\n",
    "                if to_check[to_check_index] == in_string[in_string_index]:\n",
    "                    to_check_index += 1\n",
    "\n",
    "                in_string_index += 1\n",
    "            return to_check_index == to_check_len\n",
    "    \n",
    "        source_chars = set(source)\n",
    "\n",
    "        for target_char in target:\n",
    "            if target_char not in source_chars:\n",
    "                return -1\n",
    "            \n",
    "        count = 1\n",
    "\n",
    "        new_source = source\n",
    "\n",
    "        while not _check_subsequence(target, new_source):\n",
    "            new_source += source\n",
    "\n",
    "            count +=1\n",
    "\n",
    "\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        def _check_subsequence(to_check, in_string):\n",
    "            \"\"\"\n",
    "            检查 to_check 是否是 in_string的子序列\n",
    "            :param to_check:\n",
    "            :param in_string:\n",
    "            :return:\n",
    "            \"\"\"\n",
    "            to_check_len, in_string_len = len(to_check), len(in_string)\n",
    "            to_check_index = in_string_index = 0\n",
    "\n",
    "            while to_check_index < to_check_len and in_string_index < in_string_len:\n",
    "                if to_check[to_check_index] == in_string[in_string_index]:\n",
    "                    to_check_index += 1\n",
    "                in_string_index += 1\n",
    "            return to_check_index == to_check_len\n",
    "\n",
    "        source_chars = set(source)\n",
    "\n",
    "        for target_char in target:\n",
    "            if target_char not in source_chars:\n",
    "                return -1\n",
    "\n",
    "        new_source = source\n",
    "\n",
    "        count = 1\n",
    "\n",
    "        while not _check_subsequence(target, new_source):\n",
    "            new_source += source\n",
    "            count += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubSeq(self, source: str, target: str) -> bool:\n",
    "        n, m = len(source), len(target)\n",
    "        i, j = 0,0\n",
    "        while i < n and j < m:\n",
    "            if source[i] == target[j]:\n",
    "                i+=1\n",
    "            j+=1\n",
    "        return i == n\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        # m = len(target)\n",
    "        source_set = set(source)\n",
    "        minCount = 1\n",
    "        for i in target:\n",
    "            if i not in source_set:\n",
    "                return -1\n",
    "        concatenation_source = source\n",
    "        while not self.isSubSeq(target, concatenation_source):\n",
    "            concatenation_source += source\n",
    "            minCount +=1\n",
    "        return minCount\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "\n",
    "        source_set = set([c for c in source])\n",
    "        target_set = set([c for c in target])\n",
    "        m, n = len(source), len(target)\n",
    "\n",
    "        if len(target_set.difference(source_set))>0:\n",
    "            return -1\n",
    "        elif n==0:\n",
    "            return 0\n",
    "        \n",
    "        cnt = 1\n",
    "        p, q = 0, 0\n",
    "        while q < n:\n",
    "            if p>=m:\n",
    "                p= p%m\n",
    "                cnt+=1\n",
    "            if source[p] == target[q]:\n",
    "                q+=1\n",
    "            p+=1\n",
    "        return cnt\n",
    "            \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        m,n = len(source),len(target)\n",
    "        cnt = 0\n",
    "        \n",
    "        i,j = 0,0\n",
    "\n",
    "        while j < n:\n",
    "            i = 0\n",
    "            while i < m and j < n:\n",
    "                if source[i] == target[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    if target[j] not in source:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        i += 1        \n",
    "            cnt += 1\n",
    "\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        i = 0\n",
    "        count = 0\n",
    "\n",
    "        while i < len(target):\n",
    "            subseq = 0\n",
    "            for char in source:\n",
    "                if i < len(target) and target[i] == char:\n",
    "                    i += 1\n",
    "                    subseq = 1\n",
    "            if subseq == 0:\n",
    "                return -1\n",
    "            count += 1\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#形成字符串的最短路径,贪心，模拟，双指针\n",
    "#输入：source = \"abc\", target = \"abcbc\"输出：2\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        m,n=len(source),len(target)\n",
    "        ans=0\n",
    "        j=0\n",
    "        flag=True\n",
    "        while flag:\n",
    "            flag=False\n",
    "            for i in range(m):\n",
    "                if j<n and source[i]==target[j]:\n",
    "                    flag=True\n",
    "                    j+=1\n",
    "            ans+=1\n",
    "            if j==n:break\n",
    "        return ans if j==n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        count = 0\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(target):\n",
    "            j = i\n",
    "            for c in source:\n",
    "                if i < len(target) and target[i] == c:\n",
    "                    i += 1\n",
    "            if j == i:\n",
    "                return -1\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        i,res = 0,0\n",
    "        m,n = len(source),len(target)\n",
    "        while i<n:\n",
    "            flag = True\n",
    "            res+=1\n",
    "            for j in range(m):\n",
    "                if i<n and source[j]==target[i]:\n",
    "                    i+=1\n",
    "                    flag = False\n",
    "            if flag: return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        res = 0\n",
    "        i = 0\n",
    "        pre = 0\n",
    "        while i < len(target):\n",
    "            j = 0\n",
    "            pre = i\n",
    "            while j < len(source) and i < len(target):\n",
    "                if target[i] == source[j]:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if pre == i:\n",
    "                return -1\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        res = i = 0\n",
    "        while i < len(target):\n",
    "            j = 0\n",
    "            pre = i\n",
    "            while i < len(target) and j < len(source):\n",
    "                if target[i] == source[j]:\n",
    "                    i+=1\n",
    "                j+=1\n",
    "            if pre == i:\n",
    "                return -1\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        sn, tn = len(source), len(target)\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < tn:\n",
    "            old = i\n",
    "            #---- 遍历一次source，匹配\n",
    "            j = 0\n",
    "            while i < tn and j < sn:\n",
    "                if target[i] == source[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                else:\n",
    "                    j += 1\n",
    "            #-- 1个字母也没匹配上\n",
    "            if i == old:\n",
    "                return -1\n",
    "            #-- 计数 + 1\n",
    "            res += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        charPlace = {}\n",
    "        for i in range(len(source)):\n",
    "            if source[i] in charPlace:\n",
    "                continue\n",
    "            else:\n",
    "                charPlace[source[i]] = i\n",
    "        subNum = 0\n",
    "        i,j = 0,0\n",
    "        while j < len(target):\n",
    "            if target[j] not in charPlace:\n",
    "                return -1\n",
    "            if i >= len(source):\n",
    "                subNum += 1\n",
    "                i = charPlace[target[j]]\n",
    "            if source[i] == target[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return subNum+1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        j, res = 0, 0\n",
    "\n",
    "        while j < len(target):\n",
    "            prev = j \n",
    "            for i in range(len(source)):\n",
    "                if j < len(target) and source[i] == target[j]:\n",
    "                    j += 1\n",
    "            if prev == j:\n",
    "                return -1 \n",
    "            res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        start_dic = {}\n",
    "        end_dic = {}\n",
    "\n",
    "        for i, c in enumerate(source):\n",
    "            if c not in start_dic: start_dic[c] = i\n",
    "            end_dic[c] = i\n",
    "    \n",
    "        ans, souce_index = 0, len(source)\n",
    "        for c in target:\n",
    "            if c not in start_dic: return -1\n",
    "            if end_dic[c] < souce_index: \n",
    "                souce_index = start_dic[c]+1\n",
    "                ans+=1\n",
    "            else:\n",
    "                for i in range(souce_index, end_dic[c]+1):\n",
    "                    if source[i] == c:\n",
    "                        souce_index = i+1\n",
    "                        break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        \n",
    "        # 双指针法\n",
    "        s_p = 0\n",
    "        t_p = 0\n",
    "        split_start = 0\n",
    "        ans = 0\n",
    "\n",
    "        while t_p < len(target):\n",
    "            # 对于一个新的target字符，先移动s_p找到相同的source字符\n",
    "            while s_p < len(source) and target[t_p] != source[s_p]:\n",
    "                s_p += 1\n",
    "            \n",
    "            if s_p == len(source):\n",
    "                if split_start == t_p:\n",
    "                    return -1\n",
    "                else:\n",
    "                    ans += 1\n",
    "                    s_p = 0\n",
    "                    split_start = t_p\n",
    "            else:\n",
    "                t_p += 1\n",
    "                s_p += 1\n",
    "        \n",
    "        return ans + 1\n",
    "\n",
    "            \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        m,n = len(source),len(target)\n",
    "        cnt = 0\n",
    "        \n",
    "        i,j = 0,0\n",
    "\n",
    "        while j < n:\n",
    "            i = 0\n",
    "            while i < m and j < n:\n",
    "                if source[i] == target[j]:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "                \n",
    "                if i >= m or j >= n:\n",
    "                    break\n",
    "                    \n",
    "                if source[i] != target[j]:\n",
    "                    if target[j] not in source:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        i += 1        \n",
    "            cnt += 1\n",
    "\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from copy import deepcopy\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        src_dict = defaultdict(list)\n",
    "\n",
    "        for i, w in enumerate(source):\n",
    "            src_dict[w].append(i)\n",
    "        \n",
    "        basic_dict = deepcopy(src_dict)\n",
    "        last_idx = -1\n",
    "\n",
    "        pt = 0\n",
    "\n",
    "        n = len(target)\n",
    "\n",
    "        ret = 0\n",
    "        while pt < n:\n",
    "            w = target[pt]\n",
    "\n",
    "            if w not in basic_dict:\n",
    "                return -1\n",
    "            else:\n",
    "                while True:\n",
    "                    wait_idxs = basic_dict[w]\n",
    "                    if not wait_idxs:\n",
    "                        basic_dict = deepcopy(src_dict)\n",
    "                        ret += 1\n",
    "                        last_idx = -1\n",
    "                    else:\n",
    "                        idx = bisect_left(wait_idxs, last_idx)\n",
    "                        if not wait_idxs or idx == len(wait_idxs):\n",
    "                            basic_dict = deepcopy(src_dict)\n",
    "                            ret += 1\n",
    "                            last_idx = -1\n",
    "                        else:\n",
    "                            current_idx = basic_dict[w][idx]\n",
    "                            last_idx = current_idx\n",
    "                            basic_dict[w] = basic_dict[w][idx+1:]\n",
    "                            pt += 1\n",
    "                            break\n",
    "        \n",
    "        return ret + 1\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        m = len(source)\n",
    "        n = len(target)\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        flag = True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            for i in range(m):\n",
    "                if j < n and source[i] == target[j]:\n",
    "                    flag = True\n",
    "                    j += 1\n",
    "            ans += 1\n",
    "            if j == n:\n",
    "                break\n",
    "        return ans if j == n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        sdict = {}\n",
    "        for i in range(len(source)):\n",
    "            ch = source[i]\n",
    "            if ch in sdict:\n",
    "                sdict[ch].append(i)\n",
    "            else:\n",
    "                sdict[ch] = [i]\n",
    "\n",
    "        dp = []\n",
    "        for i in range(len(target)):\n",
    "            cur = target[i]\n",
    "            if cur not in sdict:\n",
    "                return -1\n",
    "            \n",
    "            if i == 0:\n",
    "                dp.append((1, sdict[cur][0]))\n",
    "                continue\n",
    "\n",
    "            preIdx = dp[i - 1][1]\n",
    "            dp.append((dp[i - 1][0] + 1, sdict[cur][0]))\n",
    "            for curIdx in sdict[cur]:\n",
    "                if curIdx > preIdx:\n",
    "                    dp[i] = (dp[i - 1][0], curIdx)\n",
    "                    break\n",
    "        return dp[-1][0]\n",
    "\n",
    "        # w bi xt t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        memo = {}\n",
    "        def issub(s1, t1) -> bool:\n",
    "            # print(s1,t1)\n",
    "            if memo.get(t1):\n",
    "                return memo[t1]\n",
    "            if len(s1) < len(t1):\n",
    "                return False\n",
    "            idx = 0\n",
    "            for i in s1:\n",
    "                if i == t1[idx]:\n",
    "                    idx += 1\n",
    "                if idx == len(t1):\n",
    "                    break\n",
    "                \n",
    "            if idx == len(t1):\n",
    "                memo[t1] = 1\n",
    "                return True\n",
    "            return idx == len(t1)\n",
    "\n",
    "        n = len(target)\n",
    "        left = 0\n",
    "        res = 0\n",
    "        possible = False\n",
    "        while left < n:\n",
    "            # print(left)\n",
    "            curLen = 0\n",
    "            while (curLen + left < n):\n",
    "                # print(left,curLen)\n",
    "                curLen += 1\n",
    "                if (issub(source,target[left:left+curLen])):\n",
    "                    possible = True\n",
    "                else:\n",
    "                    if possible == False:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        left += (curLen-1)\n",
    "                        res += 1\n",
    "                        curLen = 0\n",
    "                        possible = False\n",
    "                        break\n",
    "            if curLen+left == n:\n",
    "                return res+1\n",
    "        return -1\n",
    "            \n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def shortestWay(self, source: str, target: str) -> int:\n",
    "#         mp = defaultdict(list)\n",
    "#         for i in range(len(source)):\n",
    "#             mp[source[i]].append(i)\n",
    "#         ans, pre = 1, -1\n",
    "#         for c in target:\n",
    "#             if c not in mp: return -1\n",
    "#             p = bisect_right(mp[c], pre)\n",
    "#             if p != len(mp[c]):\n",
    "#                 pre = mp[c][p]\n",
    "#             else:\n",
    "#                 ans += 1\n",
    "#                 pre = mp[c][0]\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        n = len(source)\n",
    "        f = [[n] * 26 for _ in range(n + 1)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(26): f[i][j] = f[i + 1][j]\n",
    "            f[i][ord(source[i]) - 97] = i\n",
    "        \n",
    "        i, j = 0, 0\n",
    "        ans = 0\n",
    "        while i < len(target):\n",
    "            ans += 1\n",
    "            while i < len(target) and f[j][ord(target[i]) - 97] != n:\n",
    "                j = f[j][ord(target[i]) - 97] + 1\n",
    "                i += 1\n",
    "            if i == len(target): return ans\n",
    "            if j == 0: return -1\n",
    "            j = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        temp = list(source)\n",
    "        res = 0\n",
    "        i = 0\n",
    "        target = list(target)\n",
    "        print(target)\n",
    "        while target:\n",
    "            popFlag = False\n",
    "            while temp and target:\n",
    "                s = temp.pop(0)\n",
    "                if s == target[0]:\n",
    "                    target.pop(0)\n",
    "                    popFlag = True\n",
    "            if not popFlag:return -1\n",
    "            res += 1\n",
    "            temp = list(source)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        n = len(source)\n",
    "        source = '#' + source\n",
    "        next = [[-1 for _ in range(26)]  for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(26):\n",
    "                next[i][j] = next[i + 1][j]\n",
    "            next[i][ord(source[i + 1]) - 97] = i + 1\n",
    "        \n",
    "        # 在source中，从当前位置i往右看，第一个char的位置记录为next[i][ch]\n",
    "        # ch为26个英文字母\n",
    "        # next成为线性状态机\n",
    "        \n",
    "        i, j = 0, 0\n",
    "        res = 1\n",
    "        while i != len(target):\n",
    "            if next[j][ord(target[i]) - 97] != -1:\n",
    "                j = next[j][ord(target[i]) - 97]\n",
    "                i += 1\n",
    "            else:\n",
    "                if j == 0:\n",
    "                    return -1\n",
    "                j = 0\n",
    "                res += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        count=1\n",
    "        t=defaultdict(list)\n",
    "\n",
    "        for i in range(len(source)):\n",
    "            t[source[i]].append(i)\n",
    "        print(t)\n",
    "        start=-1\n",
    "\n",
    "        for i in range(len(target)):\n",
    "            if target[i] not in t:\n",
    "                return -1\n",
    "            s=t[target[i]]\n",
    "            if s[-1]<=start:\n",
    "                start=s[0]\n",
    "                count+=1\n",
    "            else:\n",
    "                for c in s:\n",
    "                    if c>start:\n",
    "                        start=c\n",
    "                        break\n",
    "        return count\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def shortestWay(self, source: str, target: str) -> int:\n",
    "#         mp = defaultdict(list)\n",
    "#         for i in range(len(source)):\n",
    "#             mp[source[i]].append(i)\n",
    "#         ans, pre = 1, -1\n",
    "#         for c in target:\n",
    "#             if c not in mp: return -1\n",
    "#             p = bisect_right(mp[c], pre)\n",
    "#             if p != len(mp[c]):\n",
    "#                 pre = mp[c][p]\n",
    "#             else:\n",
    "#                 ans += 1\n",
    "#                 pre = mp[c][0]\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        n = len(source)\n",
    "        f = [[n] * 26 for _ in range(n + 1)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i] = f[i + 1][:]\n",
    "            f[i][ord(source[i]) - 97] = i\n",
    "        \n",
    "        i, j = 0, 0\n",
    "        ans = 0\n",
    "        while i < len(target):\n",
    "            ans += 1\n",
    "            while i < len(target) and f[j][ord(target[i]) - 97] != n:\n",
    "                j = f[j][ord(target[i]) - 97] + 1\n",
    "                i += 1\n",
    "            if i == len(target): return ans\n",
    "            if j == 0: return -1\n",
    "            j = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def shortestWay(self, source: str, target: str) -> int:\n",
    "#         mp = defaultdict(list)\n",
    "#         for i in range(len(source)):\n",
    "#             mp[source[i]].append(i)\n",
    "#         ans, pre = 1, -1\n",
    "#         for c in target:\n",
    "#             if c not in mp: return -1\n",
    "#             p = bisect_right(mp[c], pre)\n",
    "#             if p != len(mp[c]):\n",
    "#                 pre = mp[c][p]\n",
    "#             else:\n",
    "#                 ans += 1\n",
    "#                 pre = mp[c][0]\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def shortestWay(self, source: str, target: str) -> int:\n",
    "        n = len(source)\n",
    "        f = [[n] * 26 for _ in range(n + 1)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i] = f[i + 1][:]\n",
    "            f[i][ord(source[i]) - 97] = i\n",
    "        \n",
    "        i, j = 0, 0\n",
    "        ans = 0\n",
    "        while i < len(target):\n",
    "            ans += 1\n",
    "            while i < len(target) and f[j][ord(target[i]) - 97] != n:\n",
    "                j = f[j][ord(target[i]) - 97] + 1\n",
    "                i += 1\n",
    "            if i == len(target): return ans\n",
    "            if j == 0: return -1\n",
    "            j = 0\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
